class Solution
{
public:
    int subarraysDivByK(vector<int> &nums, int k)
    {
        unordered_map<int, int> prefixSumModKCount;
        prefixSumModKCount[0] = 1;
        int sum = 0;
        int result = 0;
        for (auto num : nums)
        {
            sum += num;
            sum = (sum % k + k) % k; // 防止负数
            result += prefixSumModKCount[sum];
            ++prefixSumModKCount[sum];
        }
        return result;
    }
};